import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/8 22:28
 * @description 动态规划
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int minimumTotal(List<List<Integer>> tri) {
        int n = tri.size();
        int ans = Integer.MAX_VALUE;
        // f[i][j]为到达某点i,j的最小路径和
        int[][] f = new int[n][n];
        f[0][0] = tri.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                int val = tri.get(i).get(j);
                f[i][j] = Integer.MAX_VALUE;
                if (j != 0) {
                    // 只要不是第一列位置上的数，都能通过左上方的数转移过来
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + val);
                }
                if (j != i) {
                    // 只要不是每行的最后一列 （j!=i)，那么都能通过上方转移过来
                    f[i][j] = Math.min(f[i][j], f[i - 1][j] + val);
                }
            }
        }
        // 最后一行的最小值
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, f[n - 1][i]);
        }
        return ans;
    }
}
